package leetcode.code0865;

import leetcode.helper.tree.TreeNode;

public class Solution extends S865 {

	class Info {
		public int deep;// 子树最深达到了deep
		public TreeNode ans;// 掌握最多这个节点的根是ans
		public int size;// ans有size个这样的节点

		public Info(int deep, int size, TreeNode ans) {
			this.deep = deep;
			this.size = size;
			this.ans = ans;
		}

	}

	@Override
	public TreeNode subtreeWithAllDeepest(TreeNode root) {
		Info info = this.f(root, 0);
		return info.ans == null ? root : info.ans;
	}

	private Info f(TreeNode root, int deep) {
		if (root.left == null && root.right == null) {
			return new Info(deep, 1, root);
		}
		Info left = null;
		Info right = null;
		if (root.left != null) {
			left = this.f(root.left, deep + 1);
		}
		if (root.right != null) {
			right = this.f(root.right, deep + 1);
		}
		if (left != null && right != null) {
			if (left.deep == right.deep)
				return new Info(left.deep, left.size + right.size, root);
			else if (left.deep > right.deep)
				return left;
		} else if (left != null) {
			return left;
		}
		return right;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
